To guarantee the communication security of Internet of Vehicles (IoV) and reduce the overhead caused by updating vehicles private key frequently, firstly, the existing certificateless aggregate signature schemes were proved vulnerable to public key replacement attacks and malevolent Key Generation Center (KGC) attack at the same time. Secondly, a certificateless aggregate signature scheme with strong privacy protection and suitable for IoV was proposed. In the proposed scheme, by introducing pseudonymous identities, vehicles’ identities were hidden and trusted authority was capable of tracing malicious vehicles after the events. Meanwhile, vehicles’ pseudonymous identities and public keys were able to be updated dynamically with the change of the area in the proposed scheme. In this way, it was not only able to ensure the safety of vehicles’ trajectories, but also able to avoid the communication and storage overhead brought by frequent private key update effectively. Under the assumption of the Elliptic Curve Discrete Logarithm (ECDL) problem, security proof shows that the proposed scheme satisfies authentication and integrity under the random oracle model. Moreover, anonymity, traceability and strong privacy protection are also provided by the proposed scheme. At the same time, aggregate signature technology was used to realize the aggregated verification of vehicle signatures in the scheme, which reduced the computational cost of verifying the signature. Performance analysis shows that when the number of signatures contained in the aggregate signature is 100, the communication overhead of transmitting aggregated signatures by the proposed scheme is reduced by at least approximately
compared with the other related schemes.